package dipl.algorithm.math.fp.geometry.op;

import dipl.algorithm.exception.ArgumentNullException;
import dipl.algorithm.math.fp.primitive.Point2df;
import dipl.algorithm.math.fp.primitive.Vector2df;
import dipl.algorithm.math.fp.primitive.op.Point2dOps;
import dipl.algorithm.math.fp.primitive.op.Vector2dOps;
import dipl.algorithm.math.primitive.Side;
import dipl.algorithm.math.primitive.Tuple2;

/**
 * Class provides utilities on 2d point sets.
 */
public  class Point2dSetOps {

	//
	// PUBLIC METHODS
	//

	/**
	 * Computes a cone with given origin containing given n-sided convex polygon.
	 * The resulting cone is given by indices of left and right ending points.
	 * It is assumed that given origin is not properly contained polygon.
	 * Running-time: O(n)
	 * param points polygon points ordered clockwise
	 * param origin origin
	 * param left
	 * param right
	 */
	public static Tuple2<Integer,Integer> ComputeCone( Point2df[] points, Point2df origin ) {
		int left; // results
		int right;
		int n = points.length;
		// easy case: first point lies on origin -> left and right are polygon edges 0 and n-1
		if( points[0].x == origin.x && points[0].y == origin.y ) {
			left = 0;
			right = n-1;
			return new Tuple2<Integer, Integer>( left, right );
		}

		// Find left bound: it is the leftmost line from origin to any polygon point when seen from origin.
		left = 0;
		Vector2df vLeft = new Vector2df(); // left vector
		Vector2df vRight = new Vector2df(); // right vector
		Vector2df vTemp = new Vector2df(); // current vector

		int i;
		vLeft.Set( points[left].x-origin.x, points[left].y-origin.y );
		for( i = 1; i < n; i++ ) {
			vTemp.Set( points[i].x-origin.x, points[i].y-origin.y );
			if( Vector2dOps.WhichSide( vLeft, vTemp ) == Side.Left ) {
				vLeft.Set( vTemp );
				left = i;
			}
		}

		// Find right bound: it is the rightmost line from origin to any polygon point when seen from origin.
		right = left;
		vRight.Set( vLeft );
		for( i = left+1; i < left+n; i++ ) {
			vTemp.Set( points[i%n].x-origin.x, points[i%n].y-origin.y );
			if( Vector2dOps.WhichSide( vRight, vTemp ) == Side.Right ) {
				vRight.Set( vTemp );
				right = i%n;
			}
		}
		return new Tuple2<Integer, Integer>( left, right );
	}

	/**
	 * Calculates convex hull of given points using Graham's scan and
	 * returns copies of the points belonging to hull in clockwise order.
	 * Running time: O(nlogn)
	 * param pointset array of points
	 * param hullSet resulting hull (<code>null</code> if number of points = 0)
	 * param leaveInputUnchanged
	 *   Whether or not to leave input array unchanged.
	 *   If <code>false</code> the ordering of points in the input array may be changed.
	 */
	public static Point2df[] ComputeConvexHull( Point2df[] pointSet, boolean leaveInputUnchanged ) {
		return ComputeConvexHull( pointSet, pointSet.length, leaveInputUnchanged );
	}

	/**
	 * Calculates convex hull of given points using Graham's scan and
	 * returns copies of the points belonging to hull in clockwise order.
	 * Running time: O(nlogn)
	 * param pointset array of points
	 * param numPoints number of points in array (may be less than length of array)
	 * param hullSet resulting hull (<code>null</code> if number of points = 0)
	 * param leaveInputUnchanged
	 *   Whether or not to leave input array unchanged.
	 *   If <code>false</code> the ordering of points in the input array may be changed.
	 */
	public static Point2df[] ComputeConvexHull( Point2df[] pointSet, int numPoints, boolean leaveInputUnchanged ) {
		// check out some nasty cases
		if( numPoints == 0 ) // no points -> no hull
			return null;

		Point2df[] hullSet = null; // resulting hull points
	
		int i; // indices
		int n = numPoints; // number of points

		if( leaveInputUnchanged ) { // create copy of input
			hullSet = new Point2df[numPoints];
			for( i = 0; i < n; i++ ) {
				hullSet[i] = pointSet[i];
			}
		}
		else {
			hullSet = pointSet;
		}

		if( n == 1 )
			return hullSet;

		// sort points lexicographically first
		SortPointsLexicographically( hullSet, numPoints );


		Point2df[] hull = new Point2df[n*2]; // hull calculated so far
		int index; // size of hull so far

		// construct upper hull

		hull[0] = hullSet[0];
		hull[1] = hullSet[1];
		index = 1;
		for( i = 2; i < n; i++ ) {
			index++;
			hull[index] = hullSet[i];
			while( index > 1 && !Point2dOps.MakeRightTurn( hull[index-2], hull[index-1], hull[index] ) ) {
				hull[index-1] = hull[index];
				index--;
			}
		}

		int upperHullSize = index+1; // hull size at this moment

		// construct lower hull
		index++;
		hull[index] = hullSet[n-2];

		for( i = n-3; i >= 0; i-- ) {
			index++;
			hull[index] = hullSet[i];
			while( index > upperHullSize && !Point2dOps.MakeRightTurn( hull[index-2], hull[index-1], hull[index] ) ) {
				hull[index-1] = hull[index];
				index--;
			}
		}
		index--; // last point is twice in list (first and last)

		// fill hullset with hull points
		hullSet = new Point2df[index+1];
		for( i = 0; i <= index; i++ ) {
			hullSet[i] = hull[i];
		}
		return hullSet;
	}

	/**
	 * Returns whether given two point-sets are equal.
	 * @param ps_a
	 * @param ps_b
	 * @return
	 * @throws ArgumentNullException one argument is null
	 */
	public static boolean AreEqual( Point2df[] ps_a, Point2df[] ps_b ) throws Exception {
		if( ps_a == null || ps_b == null )
			throw new ArgumentNullException();

		if( ps_a.length != ps_b.length )
			return false;

		int i;
		for( i = 0; i < ps_a.length; i++ ) {
			if( ps_a[i].x != ps_b[i].x || ps_a[i].y != ps_b[i].y )
				return false;
		}
		return true;
	}

	/**
	 * Returns ab, the array formed by concatenating a and b
	 * @param a
	 * @param b
	 * @return
	 */
	public static Point2df[] Concat( Point2df[] a, Point2df[] b ) {
		int n = a.length;
		int l = n+b.length;
		Point2df[] res = new Point2df[l];
		for( int i = 0; i < n; i++ ) {
			res[i] = a[i];
		}
		int j = 0;
		for( int i = n; i < l; i++ ) {
			res[i] = b[j];
			j++;
		}
		return res;
	}

	/**
	 * Special variant of concat which ignores first element of second array.
	 * Returns a(b*), the array formed by concatenating a and b* = (b1,...,bn-1)
	 * @param a
	 * @param b
	 * @return
	 */
	public static Point2df[] Concat2( Point2df[] a, Point2df[] b ) {
		int n = a.length;
		int l = n+b.length-1;
		Point2df[] res = new Point2df[l];
		for( int i = 0; i < n; i++ ) {
			res[i] = a[i];
		}
		int j = 1;
		for( int i = n; i < l; i++ ) {
			res[i] = b[j];
			j++;
		}
		return res;
	}

	/**
	 * Copies given point array and returns copy
	 * @param orig
	 * @return
	 */
	public static Point2df[] Copy( Point2df[] orig ) {
		if( orig == null )
			return null;
		Point2df[] copy = new Point2df[orig.length];
		for( int i = 0; i < orig.length; i++ ) {
			copy[i] = new Point2df( orig[i] );
		}
		return copy;
	}

	/**
	 * Returns whether given point-set actually consists of a single point.
	 * (all points are equal). If given point-set is null, false is returned.
	 * @param ps
	 * @return
	 */
	public static boolean IsOnePoint( Point2df[] ps ) {
		if( ps == null )
			return false;

		int i;
		for( i = 1; i < ps.length; i++ ) {
			if( ps[0].x != ps[i].x || ps[0].y != ps[i].y )
				return false;
		}
		return true;
	}

	/**
	 * sorts given n 2d-points in ascending order using given ordering-callback-function.
	 * The points are sorted in-situ in O(nlogn) time using heap-sort.
	 * @param points
	 */
	public static void SortPointsLexicographically( Point2df[] points ) {
		SortPointsLexicographically( points, points.length );
	}

	/**
	 * Sorts given n 2d-points in ascending order using given ordering-callback-function.
	 * The points are sorted in-situ in O(nlogn) time using heap-sort.
	 * @param points
	 * @param numPoints
	 */
	public static void SortPointsLexicographically( Point2df[] points, int numPoints ) {
		if( numPoints <= 1 )
			return;

		int len = numPoints;
		int half = (len>>1)-1; // first unsorted index
		int i; // indices
		Point2df temp;// temporary storage

		// first of all build min-heap from array
		for( i = half; i >= 0; i-- ) {
			MaxHeapSink( points, i, len );
		}

		// now sort heap
		// greatest element always is at heap root
		for( i = len-1; i > 0; i-- ) {
			// exchange root with point at index i and sink root
			temp = points[i];
			points[i] = points[0];
			points[0] = temp;
			MaxHeapSink( points, 0, i );
		}
	}

	/**
	 * Swaps indices of given point array:
	 * [0,1,...,n-1] -> [n-1,n-2,...,0]
	 * Running-time: O(n)
	 * @param pa
	 */
	public static void Swap( Point2df[] pa ) {
		int len = pa.length;
		if( len <= 1 )
			return;
		Point2df temp; // helper
		int i; // index;
		int half = len >> 1;
		for( i = 0; i < half; i++ ) {
			temp = pa[i];
			pa[i] = pa[len-i-1];
			pa[len-i-1] = temp;
		}
	}

	//
	// PRIVATE METHODS
	//

	/**
	 * Lets ith element of given point heap sink down as long as its smaller than its childs and child-index is smaller than n
	 * @param points
	 * @param i
	 * @param n
	 */
	private static void MaxHeapSink( Point2df[] points, int i, int n ) {
		int lc, rc, ci; // left and right child index, compare index
		Point2df temp;// temporary for exchanging points
		int maxIndex = (n>>1)-1; // maximal index to compare

		while( i <= maxIndex ) {
			// get child to compare
			lc = (i<<1)+1;
			rc = lc+1;

			if( lc < n && rc < n )
				ci = Point2dOps.ComparePointsLexicographically( points[lc], points[rc] ) > 0 ? lc : rc;
			else if( lc < n )
				ci = lc;
			else
				break;

			// sink into smaller child if its greater than element at index
			if( Point2dOps.ComparePointsLexicographically( points[i], points[ci] ) < 0 ) {
				temp = points[ci];
				points[ci] = points[i];
				points[i] = temp;
				i = ci;
			}
			else
				break;
		}
	}
}
